#include "BinarySearchTree.h"
using namespace std;

#include <time.h>
#include <stdlib.h>
#include <utility>
#include <ctime>

#define MAXN 1000
#define TESTN 10

//make array out of order
template <typename Comparable>
void Shuffle(std::vector<Comparable> &_arr){
	srand(time(NULL));
	int i = 0;
	for (i = _arr.size() - 1; i > 0; i --){
		int index = rand() % (i + 1);
		std::swap(_arr[i], _arr[index]);
	}
}

//sort the array _array,and output directly
template <typename Comparable>
void BSTSorting(std::vector<Comparable> &_arr, int _mode = 0){
	BinarySearchTree<Comparable> t;
	int i = 0;
	if(!_arr.empty()){
		if(_mode = 1){
			Shuffle(_arr);
		}
		for (i = 0; i < _arr.size(); i ++){
        		t.insert(_arr[i]);
		}
		//t.output(_arr);
	}
}

    // Test program
int main( ){
	vector<int> a;
	int i = 0;
	for ( i = MAXN; i > 0; i --){
		a.push_back(i);
	}
	//the worst case when _mode = 0
        clock_t startTime, endTime;
        startTime = clock();
	BSTSorting(a,0);
	endTime = clock();
	cout << "_mode = 0 : " << (double)(endTime - startTime) * 1000 / CLOCKS_PER_SEC << "ms" << endl;
	//the average case when _mode = 1
	double sumTime = 0;
	for(int n = 1; n <= TESTN; n ++){
		startTime = clock();
	        BSTSorting( a, 1);
		endTime = clock();
		double time =  (double)(endTime - startTime) * 1000 / CLOCKS_PER_SEC;
		cout << "n = " << n << ":" << time << "ms" << endl;
		sumTime = sumTime + time;
	}
	double avgTime = sumTime / TESTN;
	cout << "_mode = 1 : " <<  avgTime << "ms" << endl;
	return 0;
}

